1. Field
The present embodiments relate to techniques for facilitating concurrency control in computer systems. More specifically, the present embodiments relate to a method and system for determining memory access conflicts during concurrent execution using hierarchical Bloom filters (HBFs).
2. Related Art
Computer system designers are presently developing mechanisms to support multi-threading within the latest generation of Chip-Multiprocessors (CMPs) as well as more traditional Symmetric Multiprocessors (SMPs). With proper hardware support, multi-threading can dramatically increase computational performance. However, as microprocessor performance continues to increase, the time spent synchronizing between threads (processes) is becoming a large fraction of overall execution time. In fact, as multi-threaded applications begin to use even more threads, this synchronization overhead often becomes the dominant factor in limiting application performance.
From a programmer's perspective, synchronization is typically accomplished through the use of locks. A lock is usually acquired before a thread enters a critical section of code, and is released after the thread exits the critical section. If another thread wants to enter a critical section protected by the same lock, it must acquire the same lock. If it is unable to acquire the lock, because a preceding thread has acquired the lock, the thread must wait until the preceding thread releases the lock. (Note that a lock can be implemented in a number of ways, such as through atomic operations or semaphores.)
Unfortunately, the process of acquiring a lock and the process of releasing a lock can be very time-consuming in modern microprocessors. They typically involve atomic operations, which flush load and store buffers, and can consequently require hundreds, if not thousands, of processor cycles to complete.
Alternatively, synchronization between concurrently executing/threads may involve the use of other types of concurrency control mechanisms such as transactional execution of critical sections. Changes made during transactional execution of the critical section may not be committed to the architectural state of the processor until the transactional execution successfully completes. Furthermore, an executing transaction may not commit if a conflict is detected with a concurrently executing thread. Hence, transactional execution may boost performance by facilitating multithreading and/or multiprocessing while avoiding the overhead associated with lock-based synchronization of threads.
To detect conflicts between concurrently executing threads (or transactions), a concurrency control mechanism may generate read set signatures and write set signatures corresponding to the read sets and write sets of two or more concurrently executing threads. A conflict may occur when the same address appears in the write set signatures of two different threads and/or in the write set signature of one thread and the read set signature of another thread.
Read and write signatures may be created using Bloom filters, which store memory addresses associated with reads and writes by mapping the memory addresses to a bit array using one or more hash functions. In this way, a Bloom filter provides a compact representation of a read or write set of a thread. Moreover, conflicts between threads may be quickly detected by examining the bitwise intersection between two Bloom filters. Thus, Bloom filters may provide space and time advantages over other structures for representing read and write sets, such as linked lists, hash tables, or search trees. However, a Bloom filter may produce false positives, and such false positives may increase in frequency as elements are added to the Bloom filter. Consequently, conflict detection using Bloom filters may become unwieldy or inaccurate as read and write set signatures grow in size and complexity.
Hence, what is needed is a technique that efficiently and accurately detects conflicts in concurrently executing threads without the disadvantages of existing techniques.